//
// Created by 高森森 on 2022/2/10.
//

#ifndef LEETCODE_SOLUTION32_H
#define LEETCODE_SOLUTION32_H

#include <iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

class Solution32 {
    class ThroneInheritance {
    public:
        unordered_map<string,vector<string>>graph;
        unordered_set<string> dead;
        string king;
        ThroneInheritance(string kingName) {
            this->king=move(kingName);
        }

        void birth(string parentName, string childName) {
            graph[move(parentName)].push_back(move(childName));
        }

        void death(string name) {
            dead.insert(move(name));
        }

        vector<string> getInheritanceOrder() {
            vector<string>ans;
            dfs(king,ans);
            return ans;
        }
        void dfs(string name,vector<string>&ans){
            if(!dead.count(name))
            {
                ans.push_back(name);
            }
            for(auto child:graph[name]){
                dfs(child,ans);
            }
        }
    };
};


#endif //LEETCODE_SOLUTION32_H
